//215.数组第 k 个最大的元素。
//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。


//方法一
class Solution {
public:
    //向下调整算法
    void downheap(vector<int>& a, int i, int heapSize)
    {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            downheap(a, largest, heapSize);
        }

    }


    void makeheap(vector<int>& nums, int heapsize)
    {

        for (int father = heapsize / 2; father >= 0; --father)
        {
            downheap(nums, father, heapsize);
        }

    }



    int findKthLargest(vector<int>& nums, int k)
    {
        //建堆
        int heapSize = nums.size();
        makeheap(nums, heapSize);

        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i)
        {
            swap(nums[0], nums[i]);
            --heapSize;
            downheap(nums, 0, heapSize);
        }

        return nums[0];
    }
};


//方法二

class Solution 
{
public:

    struct Compare {
        bool operator()(int a, int b) {
            return a > b;  
        }
    };
    int findKthLargest(vector<int>& nums, int k) 
    {
        int n=nums.size();
        priority_queue<int> pq;
        for(int i=0;i<n;i++)
        {
            pq.push(nums[i]);
        }
        for(int i=0;i<k-1;i++)
        {
            pq.pop();
        }
        return pq.top();
    }
};

//方法三
class Solution {
public:
    int quickselect(vector<int>& nums,int l,int r,int k)
    {
        if (l == r) return nums[k];
        int key = nums[l];
        int lt = l; // 小于基准元素的元素的右边界
        int gt = r; // 大于基准元素的元素的左边界
        int i = l + 1; // 当前遍历的元素

        while (i <= gt) 
        {
            if (nums[i] < key) 
            {
                swap(nums[i], nums[lt]);
                lt++;
                i++;
            } 
            else if (nums[i] > key) 
            {
                swap(nums[i], nums[gt]);
                gt--;
            } else {
                i++;
            }
        }

        if (k >= lt && k <= gt) 
        {
            return nums[k];
        } else if (k < lt) {
            return quickselect(nums, l, lt - 1, k);
        } else {
            return quickselect(nums, gt + 1, r, k);
        }
    }

    int findKthLargest(vector<int>& nums, int k) 
    {
        int n=nums.size();
        return quickselect(nums,0,n-1,n-k);
    }
};